// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_ASMJS_ASM_PARSER_H_
#define V8_ASMJS_ASM_PARSER_H_

#include <memory>
#include <string>

#include "src/asmjs/asm-scanner.h"
#include "src/asmjs/asm-types.h"
#include "src/base/enum-set.h"
#include "src/vector.h"
#include "src/wasm/wasm-module-builder.h"
#include "src/zone/zone-containers.h"

namespace v8 {
namespace internal {

    class Utf16CharacterStream;

    namespace wasm {

        // A custom parser + validator + wasm converter for asm.js:
        // http://asmjs.org/spec/latest/
        // This parser intentionally avoids the portion of JavaScript parsing
        // that are not required to determine if code is valid asm.js code.
        // * It is mostly one pass.
        // * It bails out on unexpected input.
        // * It assumes strict ordering insofar as permitted by asm.js validation rules.
        // * It relies on a custom scanner that provides de-duped identifiers in two
        //   scopes (local + module wide).
        class AsmJsParser {
        public:
            // clang-format on
            enum StandardMember {
                kInfinity,
                kNaN,
#define V(_unused1, name, _unused2, _unused3) kMath##name,
                STDLIB_MATH_FUNCTION_LIST(V)
#undef V
#define V(name, _unused1) kMath##name,
                    STDLIB_MATH_VALUE_LIST(V)
#undef V
#define V(name, _unused1, _unused2, _unused3) k##name,
                        STDLIB_ARRAY_TYPE_LIST(V)
#undef V
            };
            // clang-format on

            using StdlibSet = base::EnumSet<StandardMember, uint64_t>;

            explicit AsmJsParser(Zone* zone, uintptr_t stack_limit,
                Utf16CharacterStream* stream);
            bool Run();
            const char* failure_message() const { return failure_message_; }
            int failure_location() const { return failure_location_; }
            WasmModuleBuilder* module_builder() { return module_builder_; }
            const StdlibSet* stdlib_uses() const { return &stdlib_uses_; }

        private:
            // clang-format off
  enum class VarKind {
    kUnused,
    kLocal,
    kGlobal,
    kSpecial,
    kFunction,
    kTable,
    kImportedFunction,
#define V(_unused0, Name, _unused1, _unused2) kMath##Name,
    STDLIB_MATH_FUNCTION_LIST(V)
#undef V
#define V(Name, _unused1) kMath##Name,
    STDLIB_MATH_VALUE_LIST(V)
#undef V
  };
            // clang-format on

            // A single import in asm.js can require multiple imports in wasm, if the
            // function is used with different signatures. {cache} keeps the wasm
            // imports for the single asm.js import of name {function_name}.
            struct FunctionImportInfo {
                Vector<const char> function_name;
                ZoneUnorderedMap<FunctionSig, uint32_t> cache;

                // Constructor.
                FunctionImportInfo(Vector<const char> name, Zone* zone)
                    : function_name(name)
                    , cache(zone)
                {
                }
            };

            struct VarInfo {
                AsmType* type = AsmType::None();
                WasmFunctionBuilder* function_builder = nullptr;
                FunctionImportInfo* import = nullptr;
                uint32_t mask = 0;
                uint32_t index = 0;
                VarKind kind = VarKind::kUnused;
                bool mutable_variable = true;
                bool function_defined = false;
            };

            struct GlobalImport {
                Vector<const char> import_name;
                ValueType value_type;
                VarInfo* var_info;
            };

            // Distinguish different kinds of blocks participating in {block_stack}. Each
            // entry on that stack represents one block in the wasm code, and determines
            // which block 'break' and 'continue' target in the current context:
            //  - kRegular: The target of a 'break' (with & without identifier).
            //              Pushed by an IterationStatement and a SwitchStatement.
            //  - kLoop   : The target of a 'continue' (with & without identifier).
            //              Pushed by an IterationStatement.
            //  - kNamed  : The target of a 'break' with a specific identifier.
            //              Pushed by a BlockStatement.
            //  - kOther  : Only used for internal blocks, can never be targeted.
            enum class BlockKind { kRegular,
                kLoop,
                kNamed,
                kOther };

            // One entry in the {block_stack}, see {BlockKind} above for details. Blocks
            // without a label have {kTokenNone} set as their label.
            struct BlockInfo {
                BlockKind kind;
                AsmJsScanner::token_t label;
            };

            // Helper class to make {TempVariable} safe for nesting.
            class TemporaryVariableScope;

            template <typename T>
            class CachedVectors {
            public:
                explicit CachedVectors(Zone* zone)
                    : reusable_vectors_(zone)
                {
                }

                Zone* zone() const { return reusable_vectors_.get_allocator().zone(); }

                inline void fill(ZoneVector<T>* vec)
                {
                    if (reusable_vectors_.empty())
                        return;
                    reusable_vectors_.back().swap(*vec);
                    reusable_vectors_.pop_back();
                    vec->clear();
                }

                inline void reuse(ZoneVector<T>* vec)
                {
                    reusable_vectors_.emplace_back(std::move(*vec));
                }

            private:
                ZoneVector<ZoneVector<T>> reusable_vectors_;
            };

            template <typename T>
            class CachedVector final : public ZoneVector<T> {
            public:
                explicit CachedVector(CachedVectors<T>& cache)
                    : ZoneVector<T>(cache.zone())
                    , cache_(&cache)
                {
                    cache.fill(this);
                }
                ~CachedVector() { cache_->reuse(this); }

            private:
                CachedVectors<T>* cache_;
            };

            Zone* zone_;
            AsmJsScanner scanner_;
            WasmModuleBuilder* module_builder_;
            WasmFunctionBuilder* current_function_builder_;
            AsmType* return_type_;
            uintptr_t stack_limit_;
            StdlibSet stdlib_uses_;
            ZoneVector<VarInfo> global_var_info_;
            ZoneVector<VarInfo> local_var_info_;

            CachedVectors<ValueType> cached_valuetype_vectors_ { zone_ };
            CachedVectors<AsmType*> cached_asm_type_p_vectors_ { zone_ };
            CachedVectors<AsmJsScanner::token_t> cached_token_t_vectors_ { zone_ };
            CachedVectors<int32_t> cached_int_vectors_ { zone_ };

            int function_temp_locals_offset_;
            int function_temp_locals_used_;
            int function_temp_locals_depth_;

            // Error Handling related
            bool failed_;
            const char* failure_message_;
            int failure_location_;

            // Module Related.
            AsmJsScanner::token_t stdlib_name_;
            AsmJsScanner::token_t foreign_name_;
            AsmJsScanner::token_t heap_name_;

            static const AsmJsScanner::token_t kTokenNone = 0;

            // Track if parsing a heap assignment.
            bool inside_heap_assignment_;
            AsmType* heap_access_type_;

            ZoneVector<BlockInfo> block_stack_;

            // Types used for stdlib function and their set up.
            AsmType* stdlib_dq2d_;
            AsmType* stdlib_dqdq2d_;
            AsmType* stdlib_i2s_;
            AsmType* stdlib_ii2s_;
            AsmType* stdlib_minmax_;
            AsmType* stdlib_abs_;
            AsmType* stdlib_ceil_like_;
            AsmType* stdlib_fround_;

            // When making calls, the return type is needed to lookup signatures.
            // For `+callsite(..)` or `fround(callsite(..))` use this value to pass
            // along the coercion.
            AsmType* call_coercion_;

            // The source position associated with the above {call_coercion}.
            size_t call_coercion_position_;

            // When making calls, the coercion can also appear in the source stream
            // syntactically "behind" the call site. For `callsite(..)|0` use this
            // value to flag that such a coercion must happen.
            AsmType* call_coercion_deferred_;

            // The source position at which requesting a deferred coercion via the
            // aforementioned {call_coercion_deferred} is allowed.
            size_t call_coercion_deferred_position_;

            // The code position of the last heap access shift by an immediate value.
            // For `heap[expr >> value:NumericLiteral]` this indicates from where to
            // delete code when the expression is used as part of a valid heap access.
            // Will be set to {kNoHeapAccessShift} if heap access shift wasn't matched.
            size_t heap_access_shift_position_;
            uint32_t heap_access_shift_value_;
            static const size_t kNoHeapAccessShift = -1;

            // Used to track the last label we've seen so it can be matched to later
            // statements it's attached to.
            AsmJsScanner::token_t pending_label_;

            // Global imports. The list of imported variables that are copied during
            // module instantiation into a corresponding global variable.
            ZoneLinkedList<GlobalImport> global_imports_;

            Zone* zone() { return zone_; }

            inline bool Peek(AsmJsScanner::token_t token)
            {
                return scanner_.Token() == token;
            }

            inline bool Check(AsmJsScanner::token_t token)
            {
                if (scanner_.Token() == token) {
                    scanner_.Next();
                    return true;
                } else {
                    return false;
                }
            }

            inline bool CheckForZero()
            {
                if (scanner_.IsUnsigned() && scanner_.AsUnsigned() == 0) {
                    scanner_.Next();
                    return true;
                } else {
                    return false;
                }
            }

            inline bool CheckForDouble(double* value)
            {
                if (scanner_.IsDouble()) {
                    *value = scanner_.AsDouble();
                    scanner_.Next();
                    return true;
                } else {
                    return false;
                }
            }

            inline bool CheckForUnsigned(uint32_t* value)
            {
                if (scanner_.IsUnsigned()) {
                    *value = scanner_.AsUnsigned();
                    scanner_.Next();
                    return true;
                } else {
                    return false;
                }
            }

            inline bool CheckForUnsignedBelow(uint32_t limit, uint32_t* value)
            {
                if (scanner_.IsUnsigned() && scanner_.AsUnsigned() < limit) {
                    *value = scanner_.AsUnsigned();
                    scanner_.Next();
                    return true;
                } else {
                    return false;
                }
            }

            inline AsmJsScanner::token_t Consume()
            {
                AsmJsScanner::token_t ret = scanner_.Token();
                scanner_.Next();
                return ret;
            }

            void SkipSemicolon();

            VarInfo* GetVarInfo(AsmJsScanner::token_t token);
            uint32_t VarIndex(VarInfo* info);
            void DeclareGlobal(VarInfo* info, bool mutable_variable, AsmType* type,
                ValueType vtype,
                const WasmInitExpr& init = WasmInitExpr());
            void DeclareStdlibFunc(VarInfo* info, VarKind kind, AsmType* type);
            void AddGlobalImport(Vector<const char> name, AsmType* type, ValueType vtype,
                bool mutable_variable, VarInfo* info);

            // Allocates a temporary local variable. The given {index} is absolute within
            // the function body, consider using {TemporaryVariableScope} when nesting.
            uint32_t TempVariable(int index);

            // Preserves a copy of the scanner's current identifier string in the zone.
            Vector<const char> CopyCurrentIdentifierString();

            // Use to set up block stack layers (including synthetic ones for if-else).
            // Begin/Loop/End below are implemented with these plus code generation.
            void BareBegin(BlockKind kind, AsmJsScanner::token_t label = 0);
            void BareEnd();
            int FindContinueLabelDepth(AsmJsScanner::token_t label);
            int FindBreakLabelDepth(AsmJsScanner::token_t label);

            // Use to set up actual wasm blocks/loops.
            void Begin(AsmJsScanner::token_t label = 0);
            void Loop(AsmJsScanner::token_t label = 0);
            void End();

            void InitializeStdlibTypes();

            FunctionSig* ConvertSignature(AsmType* return_type,
                const ZoneVector<AsmType*>& params);

            void ValidateModule(); // 6.1 ValidateModule
            void ValidateModuleParameters(); // 6.1 ValidateModule - parameters
            void ValidateModuleVars(); // 6.1 ValidateModule - variables
            void ValidateModuleVar(bool mutable_variable);
            void ValidateModuleVarImport(VarInfo* info, bool mutable_variable);
            void ValidateModuleVarStdlib(VarInfo* info);
            void ValidateModuleVarNewStdlib(VarInfo* info);
            void ValidateModuleVarFromGlobal(VarInfo* info, bool mutable_variable);

            void ValidateExport(); // 6.2 ValidateExport
            void ValidateFunctionTable(); // 6.3 ValidateFunctionTable
            void ValidateFunction(); // 6.4 ValidateFunction
            void ValidateFunctionParams(ZoneVector<AsmType*>* params);
            void ValidateFunctionLocals(size_t param_count,
                ZoneVector<ValueType>* locals);
            void ValidateStatement(); // 6.5 ValidateStatement
            void Block(); // 6.5.1 Block
            void ExpressionStatement(); // 6.5.2 ExpressionStatement
            void EmptyStatement(); // 6.5.3 EmptyStatement
            void IfStatement(); // 6.5.4 IfStatement
            void ReturnStatement(); // 6.5.5 ReturnStatement
            bool IterationStatement(); // 6.5.6 IterationStatement
            void WhileStatement(); // 6.5.6 IterationStatement - while
            void DoStatement(); // 6.5.6 IterationStatement - do
            void ForStatement(); // 6.5.6 IterationStatement - for
            void BreakStatement(); // 6.5.7 BreakStatement
            void ContinueStatement(); // 6.5.8 ContinueStatement
            void LabelledStatement(); // 6.5.9 LabelledStatement
            void SwitchStatement(); // 6.5.10 SwitchStatement
            void ValidateCase(); // 6.6. ValidateCase
            void ValidateDefault(); // 6.7 ValidateDefault
            AsmType* ValidateExpression(); // 6.8 ValidateExpression
            AsmType* Expression(AsmType* expect); // 6.8.1 Expression
            AsmType* NumericLiteral(); // 6.8.2 NumericLiteral
            AsmType* Identifier(); // 6.8.3 Identifier
            AsmType* CallExpression(); // 6.8.4 CallExpression
            AsmType* MemberExpression(); // 6.8.5 MemberExpression
            AsmType* AssignmentExpression(); // 6.8.6 AssignmentExpression
            AsmType* UnaryExpression(); // 6.8.7 UnaryExpression
            AsmType* MultiplicativeExpression(); // 6.8.8 MultiplicativeExpression
            AsmType* AdditiveExpression(); // 6.8.9 AdditiveExpression
            AsmType* ShiftExpression(); // 6.8.10 ShiftExpression
            AsmType* RelationalExpression(); // 6.8.11 RelationalExpression
            AsmType* EqualityExpression(); // 6.8.12 EqualityExpression
            AsmType* BitwiseANDExpression(); // 6.8.13 BitwiseANDExpression
            AsmType* BitwiseXORExpression(); // 6.8.14 BitwiseXORExpression
            AsmType* BitwiseORExpression(); // 6.8.15 BitwiseORExpression
            AsmType* ConditionalExpression(); // 6.8.16 ConditionalExpression
            AsmType* ParenthesizedExpression(); // 6.8.17 ParenthesiedExpression
            AsmType* ValidateCall(); // 6.9 ValidateCall
            bool PeekCall(); // 6.9 ValidateCall - helper
            void ValidateHeapAccess(); // 6.10 ValidateHeapAccess
            void ValidateFloatCoercion(); // 6.11 ValidateFloatCoercion

            // Used as part of {ForStatement}. Scans forward to the next `)` in order to
            // skip over the third expression in a for-statement. This is one piece that
            // makes this parser not be a pure single-pass.
            void ScanToClosingParenthesis();

            // Used as part of {SwitchStatement}. Collects all case labels in the current
            // switch-statement, then resets the scanner position. This is one piece that
            // makes this parser not be a pure single-pass.
            void GatherCases(ZoneVector<int32_t>* cases);
        };

    } // namespace wasm
} // namespace internal
} // namespace v8

#endif // V8_ASMJS_ASM_PARSER_H_
